Search results for "Complete graph"
showing 9 items of 9 documents
Efficient Online Laplacian Eigenmap Computation for Dimensionality Reduction in Molecular Phylogeny via Optimisation on the Sphere
2019
Reconstructing the phylogeny of large groups of large divergent genomes remains a difficult problem to solve, whatever the methods considered. Methods based on distance matrices are blocked due to the calculation of these matrices that is impossible in practice, when Bayesian inference or maximum likelihood methods presuppose multiple alignment of the genomes, which is itself difficult to achieve if precision is required. In this paper, we propose to calculate new distances for randomly selected couples of species over iterations, and then to map the biological sequences in a space of small dimension based on the partial knowledge of this genome similarity matrix. This mapping is then used …
Grover Search with Lackadaisical Quantum Walks
2015
The lazy random walk, where the walker has some probability of staying put, is a useful tool in classical algorithms. We propose a quantum analogue, the lackadaisical quantum walk, where each vertex is given $l$ self-loops, and we investigate its effects on Grover's algorithm when formulated as search for a marked vertex on the complete graph of $N$ vertices. For the discrete-time quantum walk using the phase flip coin, adding a self-loop to each vertex boosts the success probability from 1/2 to 1. Additional self-loops, however, decrease the success probability. Using instead the Ambainis, Kempe, and Rivosh (2005) coin, adding self-loops simply slows down the search. These coins also diffe…
Minimum node weight spanning trees searching algorithm for broadcast transmission in sensor networks
2017
A minimum node weight spanning tree in a weighted, directed graph is a tree whose node with maximum out-weight is minimal among all spanning trees. This type of trees are important because they appear in the solutions of the maximum lifetime broadcasting problem in wireless sensor networks. In a complete graph build of N nodes there are NN-2 spanning trees and to find such trees it is necessary to perform more than O(NN-2) operations. In this paper we propose an algorithm for searching the minimum node weight spanning trees in the graph. In the proposed algorithm, instead of calculating the symbolic determinant of the generalized Laplacian matrix, numerical operations on its exponents are p…
Quantum Walk Search on Johnson Graphs
2016
The Johnson graph $J(n,k)$ is defined by $n$ symbols, where vertices are $k$-element subsets of the symbols, and vertices are adjacent if they differ in exactly one symbol. In particular, $J(n,1)$ is the complete graph $K_n$, and $J(n,2)$ is the strongly regular triangular graph $T_n$, both of which are known to support fast spatial search by continuous-time quantum walk. In this paper, we prove that $J(n,3)$, which is the $n$-tetrahedral graph, also supports fast search. In the process, we show that a change of basis is needed for degenerate perturbation theory to accurately describe the dynamics. This method can also be applied to general Johnson graphs $J(n,k)$ with fixed $k$.
Stochastic collision model approach to transport phenomena in quantum networks
2021
Abstract Noise-assisted transport phenomena highlight the nontrivial interplay between environmental effects and quantum coherence in achieving maximal efficiency. Due to the complexity of biochemical systems and their environments, effective open quantum system models capable of providing physical insights on the presence and role of quantum effects are highly needed. In this paper, we introduce a new approach that combines an effective quantum microscopic description with a classical stochastic one. Our stochastic collision model (SCM) describes both Markovian and non-Markovian dynamics without relying on the weak coupling assumption. We investigate the consequences of spatial and tempora…
Completely independent spanning trees in some regular graphs
2014
International audience; Let k >= 2 be an integer and T-1,..., T-k be spanning trees of a graph G. If for any pair of vertices {u, v} of V(G), the paths between u and v in every T-i, 1 <= i <= k, do not contain common edges and common vertices, except the vertices u and v, then T1,... Tk are completely independent spanning trees in G. For 2k-regular graphs which are 2k-connected, such as the Cartesian product of a complete graph of order 2k-1 and a cycle, and some Cartesian products of three cycles (for k = 3), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always k. (C) 2016 Elsevier B.V. All righ…
Correcting for Potential Barriers in Quantum Walk Search
2015
A randomly walking quantum particle searches in Grover's $\Theta(\sqrt{N})$ iterations for a marked vertex on the complete graph of $N$ vertices by repeatedly querying an oracle that flips the amplitude at the marked vertex, scattering by a "coin" flip, and hopping. Physically, however, potential energy barriers can hinder the hop and cause the search to fail, even when the amplitude of not hopping decreases with $N$. We correct for these errors by interpreting the quantum walk search as an amplitude amplification algorithm and modifying the phases applied by the coin flip and oracle such that the amplification recovers the $\Theta(\sqrt{N})$ runtime.
Enumerating the Walecki-Type Hamiltonian Cycle Systems
2017
Let Kv be the complete graph on v vertices. A Hamiltonian cycle system of odd order v (briefly HCS(v)) is a set of Hamiltonian cycles of Kv whose edges partition the edge set of Kv. By means of a slight modification of the famous HCS(4n+1) of Walecki, we obtain 2n pairwise distinct HCS(4n+1) and we enumerate them up to isomorphism proving that this is equivalent to count the number of binary bracelets of length n, i.e. the orbits of Dn, the dihedral group of order 2n, acting on binary n-tuples.
Two Parallel Algorithms for the Analysis of Random Images
1988
Aim of the paper is to show a computational paradigm, that reduces some algorithms on undirected graphs into image analysis algorithms. In particular two parallel algorithms on undirected weighted graphs, often used in the analysis of sparse images, are described.